package com.chenwut.algorithmQuestion.dataStructureAlgorithm;


import java.util.Arrays;

public class QuickSortTest {
    public static void main(String[] args) {
        int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    private static void quickSort(int[] arr, int left, int right) {
        int start = left + 1;
        int end = right;
        int pivot = arr[left];
        System.out.println(pivot);

        if (start>end){
            return;
        }

        while (start < end) {
            while (start < end && arr[end] >= pivot) {
                end--;
            }
            while (start < end && arr[start] <= pivot) {
                start++;
            }
            swap(arr, start, end);
        }

        swap(arr, left, start);

        quickSort(arr, left, end - 1);
        quickSort(arr, end + 1, right);

    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
